Offering readings from 50 of the most eminent contributors to psychology, this text-reader represents the historical development of psychology from the Renaissance to the present. Contributors range from Descartes, Locke, Hume, Kant, and Darwin through Adler, Tolman, Guthrie, Hull, and Skinner. "Far and away the most concise and pedagogically useful book of its kind ever to appear." --Psychological Record.

First published in 2005. Routledge is an imprint of Taylor & Francis, an informa company.

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals on (...) Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14. (shrink)

It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low (...) degree. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted. (shrink)

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...) n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).

We settle a question in the literature about degrees of models of true arithmetic and upper bounds for the arithmetic sets. We prove that there is a model of true arithmetic whose degree is not a uniform upper bound for the arithmetic sets. The proof involves two forcing constructions.

We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, A is a countable structure with finite signature, and d is a degree, we say that A has αth-jump degree d if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of A with universe ω in (...) which the functions and relations have degree at most c. We show that every degree d ≥ 0 (ω) is the ωth jump degree of a Boolean algebra, but that for $n no Boolean algebra has nth-jump degree $\mathbf{d} > 0^{(n)}$ . The former result follows easily from work of L. Feiner. The proof of the latter result uses the forcing methods of J. Knight together with an analysis of various equivalences between Boolean algebras based on a study of their Stone spaces. A byproduct of the proof is a method for constructing Stone spaces with various prescribed properties. (shrink)

A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that Q(X) implies that X has (...) a certain "slowness" property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ∈ ε there exists B in the orbit of A such that X ≤ T B under relative Turing computability (≤ T ). We produce B using the Δ 0 3 -automorphism method we introduced earlier. (shrink)

In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...) generalize the older results and which include positive results on when a certain homogeneous model of T has an isomorphic copy of a given Turing degree. We then survey Lange's "A characterization of the 0-basis homogeneous bounding degrees" for negative results about when does not have such copies, generalizing negative results by Goncharov, Peretyat'kin, and Millar. Finally, we explain recent results by Csima, Harizanov, Hirschfeldt, and Soare, "Bounding homogeneous models," about degrees d that are homogeneous bounding and explain their relation to the PA degrees. (shrink)

Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties (...) of A , like maximal, hh-simple, atomless, to the information content of A . Harrington and Soare gave an answer to Post's program for definable properties by producing an ∄-definable property Q which guarantees that A is incomplete and noncomputable, but developed a new Δ 3 0 -automorphism method to prove certain other properties are not ∄-definable. In this paper we introduce new ∄-definable properties relating the ∄-structure of A to deg, which answer some open questions. In contrast to Q we exhibit here an ∄-definable property T which allows such a rapid flow of elements into A that A must be complete even though A may possess many other properties such as being promptly simple. We also present a related property NL which has a slower flow but fast enough to guarantee that A is not low, even though A may possess virtually all other related lowness properties and A may simultaneously be promptly simple. (shrink)

In [2] we constructed an infinite set of natural numbers containing no subset of higher (Turing) degree. Since it is well known that there are nonrecursive sets (e.g. sets of minimal degree) containing no nonrecursive subset of lower degree, it is natural to suppose that these arguments may be combined, but this is false. We prove that every infinite set must contain a nonrecursive subset of either higher or lower degree.

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating (...) properties. Although these computability results had been announced earlier, their proofs have been deferred until this paper. Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima. (shrink)

If A and B are subsets of natural numbers we say that A is recursively equivalent to B (denoted A ≃ B) if there is a one-one partial recursive function which maps A onto B, and that A is recursively isomorphic to B (denoted A ≅ B) if there is a one-one total recursive function which maps A onto B and Ā (the complement of A) onto B#x00AF;.

J. N. Crossley [1] raised the question of whether the implication 2 + A = A ⇒ 1 + A = A is true for constructive order types (C.O.T.'s). Using an earlier definition of constructive order type, A. G. Hamilton [2] presented a counterexample. Hamilton left open the general question, however, since he pointed out that Crossley considers only orderings which can be embedded in a standard dense r.e. ordering by a partial recursive function, and that his counterexample fails to (...) meet this requirement. We resolve the question by finding a C.O.T. A which meets Crossley's requirement and such that 2 + A = A but 1 + A ≠ A. At the suggestion of A. B. Manaster and A. G. Hamilton we easily extend this construction to show that for any n ≧ 2, there is a C.O.T. A such that n + A = A but m + A ≠ A for 0 < m < n. Hence, Theorem 3 of [2] and all of its corollaries hold with the new definition of C.O.T. The construction is not difficult and requires no priority argument. The techniques are similar to those developed in [3], but no outside results are needed here. (shrink)

Despite recent advances in HIV prevention and treatment, high HIV incidence persists among people who inject drugs. Difficult legal and political environments and lack of services for PWID likely contribute to high HIV incidence. Some advocates question whether any HIV prevention research is ethically justified in settings where healthcare system fails to provide basic services to PWID and where implementation of research findings is fraught with political barriers. Ethical challenges in research with PWID include concern about whether research evidence will (...) be translated into practice; concerns that research might exacerbate background risks; and ethical challenges regarding the standard of HIV prevention in research. While these questions arise in other research settings, for research with PWID, these questions are especially controversial. This paper analyses four ethical questions in determining whether research could be ethically acceptable: Can researchers ensure that research does not add to the burden of social harms and poor health experienced by PWID? Should research be conducted in settings where it is uncertain whether research findings will be translated into practice? When best practices in prevention and care are not locally available, what standard of care and prevention is ethically appropriate? Does the conduct of research in settings with oppressive policies constitute complicity? We outline specific criteria to address these four ethical challenges. We also urge researchers to join the call to action for policy change to provide proven safe and effective HIV prevention and harm reduction interventions for PWID around the world. (shrink)

Despite recent advances in HIV prevention and treatment, high HIV incidence persists among people who inject drugs. Difficult legal and political environments and lack of services for PWID likely contribute to high HIV incidence. Some advocates question whether any HIV prevention research is ethically justified in settings where healthcare system fails to provide basic services to PWID and where implementation of research findings is fraught with political barriers. Ethical challenges in research with PWID include concern about whether research evidence will (...) be translated into practice; concerns that research might exacerbate background risks; and ethical challenges regarding the standard of HIV prevention in research. While these questions arise in other research settings, for research with PWID, these questions are especially controversial. This paper analyses four ethical questions in determining whether research could be ethically acceptable: Can researchers ensure that research does not add to the burden of social harms and poor health experienced by PWID? Should research be conducted in settings where it is uncertain whether research findings will be translated into practice? When best practices in prevention and care are not locally available, what standard of care and prevention is ethically appropriate? Does the conduct of research in settings with oppressive policies constitute complicity? We outline specific criteria to address these four ethical challenges. We also urge researchers to join the call to action for policy change to provide proven safe and effective HIV prevention and harm reduction interventions for PWID around the world. (shrink)

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

This functional Magnetic Resonance Imaging study investigated high and low suggestible people responding to two visual hallucination suggestions with and without a hypnotic induction. Participants in the study were asked to see color while looking at a grey image, and to see shades of grey while looking at a color image. High suggestible participants reported successful alterations in color perception in both tasks, both in and out of hypnosis, and showed a small benefit if hypnosis was induced. Low suggestible people (...) could not perform the tasks successfully with or without the hypnotic induction. The fMRI results supported the self report data, and changes in brain activity were found in a number of visual areas. The results indicate that a hypnotic induction, although having the potential to enhance the ability of high suggestible people, is not necessary for the effective alteration of color perception by suggestion. (shrink)

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

In crafting our paper on addressing the ethical challenges in HIV prevention research with people who inject drugs,1 we had hoped to stimulate further discussion and deliberation about the topic. We are pleased that three commentaries on our paper have begun this process.2 3 4 The commentaries rightly bring up important issues relating to community engagement and problems in translating research into practice in the fraught environments in which PWID face multiple risks. These risks include acquisition of HIV as well (...) as criminalisation, stigma and lack of access to needed healthcare, prevention and social services. We take this opportunity to respond to the excellent points raised by the commentators. All of the commentaries support our emphasis on robust community engagement with PWID and other stakeholders in designing and conducting HIV prevention research, but urge us to go farther. Wolfe highlights the difficulty of even engaging with community members in oppressive settings, where authorities severely restrict civil liberties of PWID so that even discussing issues related to drug use and enforcement may place individuals at risk. To overcome such limitations, he appropriately suggests interviewing confidentially those who have previously been detained in closed settings as part of the community engagement process. Similarly, Wolfe observes that critical issues can be overlooked with a narrow focus on study procedures if contextual factors before, during or after a study are ignored. For example, he cites the risk of overdose for study participants who have been abstinent during a study and subsequently resume injecting when the study concludes. These kinds of risks may not be obvious …. (shrink)

In crafting our paper on addressing the ethical challenges in HIV prevention research with people who inject drugs, 1 we had hoped to stimulate further discussion and deliberation about the topic. We are pleased that three commentaries on our paper have begun this process. 2 3 4 The commentaries rightly bring up important issues relating to community engagement and problems in translating research into practice in the fraught environments in which PWID face multiple risks. These risks include acquisition of HIV (...) as well as criminalisation, stigma and lack of access to needed healthcare, prevention and social services. We take this opportunity to respond to the excellent points raised by the commentators. All of the commentaries support our emphasis on robust community engagement with PWID and other stakeholders in designing and conducting HIV prevention research, but urge us to go farther. Wolfe highlights the... (shrink)

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...) X is $low_2$ if $X\prime\prime$ $\leq_{T} 0\prime$ . To prove that a $low_2$ set X is not prime bounding we use a $0\prime$ -computable listing of the array of sets { Y : Y $\leq_{T}$ X } to build a CAD theory T which diagonalizes against all potential X-decidable prime models U of T. To prove that any $non-low_{2}$ ; X is indeed prime bounding, we fix a function f $\leq_T$ X that is not dominated by a certain $0\prime$ -computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula $\varphi (\bar{x})$ consistent with T, a principal type which contains it, and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory. (shrink)

It is shown that, if a, b are recursively enumerable degrees such that 0

Logic and Philosophy of Logic

Logic and Philosophy of Logic, Miscellaneous in Logic and Philosophy of Logic

Model Theory in Logic and Philosophy of Logic

Direct download (4 more)  

 

Export citation  

 

Bookmark   6 citations  

Ethical climate (EC) has been broadly described as how well institutions respond to ethical issues. Developing a tool to study and evaluate EC that aims to achieve sustained improvements requires a contemporary framework with identified relevant drivers. An extensive literature review was performed, reviewing existing EC definitions, tools and areas where EC has been studied; ethical challenges and relevance of EC in contemporary paediatric intensive care (PIC); and relevant ethical theories. We surmised that existing EC definitions and tools designed to (...) measure it fail to capture nuances of the PIC environment, and sought to address existing gaps by developing an EC framework for PIC founded on ethical theory. In this article, we propose a Paediatric Intensive Care Ethical Climate (PICEC) conceptual framework and four measurable domains to be captured by an assessment tool. We define PICEC as the collective felt experience of interdisciplinary team members arising from those factors that enable or constrain their ability to navigate ethical aspects of their work. PICEC both results from and is influenced by how well ethical issues are understood, identified, explored, reflected on, responded to and addressed in the workplace. PICEC encompasses four, core inter-related domains representing drivers of EC including: (1) organisational culture and leadership; (2) interdisciplinary team relationships and dynamics; (3) integrated child and family-centred care; and (4) ethics literacy. Future directions involve developing a PICEC measurement tool, with implications for benchmarking as well as guidance for, and evaluation of, targeted interventions to foster a healthy EC. (shrink)

We administered suggestions to see a gray-scale pattern as colored and a colored pattern in shades of gray to 30 high suggestible and eight low suggestible students. The suggestions were administered twice, once following the induction of hypnosis and once without an induction. Besides rating the degree of color they saw in the stimuli differently, participants also rated their states of consciousness as normal, relaxed, hypnotized, or deeply hypnotized. Reports of being hypnotized were limited to highly suggestible participants and only (...) after the hypnotic induction had been administered. Reports of altered color perception were also limited to high suggestibles, but were roughly comparable regardless of whether hypnosis had been induced. These data indicate that suggestible individuals do not slip into a hypnotic state when given imaginative suggestions without the induction of hypnosis, but nevertheless report experiencing difficult suggestions for profound perceptual alterations that are pheonomenologically similar to what they report in hypnosis. (shrink)

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...) single CD theory T such that every homogeneous model of T has a PA degree. (shrink)